package alogrithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/24 21:31
 */
public class ShoppingOffers {

    // 用来进行记忆化搜索, 存储那些已经计算过的问题, 防止重复计算
    Map<List<Integer>, Integer> map = new HashMap<>();

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int n = price.size();

        // 过滤那些不要用到的礼包, 只计算那些可以被用到的礼包
        List<List<Integer>> filterSpecial = new ArrayList<>();
        for (List<Integer> sp : special) {
            // 代表该礼包中的拥有的该件物品的数量
            int totalCount = 0;
            // 代表以正常价购买这里面的物品的价格
            int totalPrice = 0;
            for (int i = 0; i < n; ++i) {
                totalCount += sp.get(i);
                totalPrice += sp.get(i) * price.get(i);
            }
            if (totalCount > 0 && totalPrice > sp.get(n)) {
                filterSpecial.add(sp);
            }
        }
        return dfs(price, filterSpecial, needs, n);
    }

    private int dfs(List<Integer> price, List<List<Integer>> filterSpecial, List<Integer> needs, int n) {
        if (!map.containsKey(needs)) {
            int minPrice = 0;
            // 首先计算不购买任何礼包的所需价格
            for (int i = 0; i < n; ++i) {
                minPrice += price.get(i) * needs.get(n);
            }

            // 然后遍历每个礼包, 算出如果买礼包的话, 所需的价格
            for (List<Integer> currSpecial : filterSpecial) {
                int currPrice = currSpecial.get(n);
                // 这是记录的是买完礼包后, 还需要第i种物品的个数
                List<Integer> nextNeeds = new ArrayList<>();
                for (int i = 0; i < n; ++i) {
                    // 礼包的数量不能大于所需要的数量
                    if (currSpecial.get(i) > needs.get(i)) {
                        break;
                    }
                    nextNeeds.add(needs.get(i) - currSpecial.get(i));
                }
                // 如果当前礼包可以购买,就更新最小价格, 然后继续往下递归, 因为礼包可以重复购买
                if (nextNeeds.size() == n) {
                    minPrice = Math.min(minPrice, dfs(price, filterSpecial, nextNeeds, n) + currPrice);
                }
            }
            map.put(needs, minPrice);
        }
        return map.get(needs);
    }
}
